class Solution:
    def maxProfit(self, prices) -> int:

        # 自底部向上
        dp_i_0 = 0
        dp_i_1 = -float("INF")
        for i in prices:
            dp_i_0,dp_i_1= max(dp_i_0,dp_i_1+i),max(dp_i_1,-i)
        return dp_i_0
if __name__ == '__main__':
    s = Solution()
    print(s.maxProfit([7, 1, 5, 3, 6, 4]))